G-systems and divisibility

Popis: D:\binary\images\d_gdivi.jpg



Divisibility in G(n,k)

Instance number u(i,j) is divisible with r=(n^k-1) just if corresponding class number g(i) is divisible with r. The number of all numbers that are not divisible with r is φ(r), where φ is Euler function.

If g(i) is not divisible with r, then its class must be the self class (not nested) and such class has k instances.
Therefore:

   φ(n^k-1) mod k = 0

E-classes are classes satisfying:

   gcd(g,r)=1

where gcd() denotes the greatest common divisor. For example φ(2^4-1) = φ(15) = 8 (see rows marked by asterisk).

G(2,4)
  0
* 1  2  4  8
  3  6 12  9
  5 10
* 7 14 13 11
 15

We see that 8 mod 4 = 0.

G-quotient g(n,k) = φ(n^k-1)/k

  n \ k |  1   2    3    4    5    6    7    8    9   10
  --------------------------------------------------------
    1   |  -   -    -    -    -   -    -     -    -    -
    2   |  1   1    2    2    6    6   18   16   48   60
    3   |  1   2    4    8   22   48  156  320 1008
    4   |  1   4   12   32  120  288 1512 4096
    5   |  2   4   20   48  280  720 5580
    6   |  4  12   56  216 1240
    7   |  2   8   36  160
    8   |  6  18  144
    9   |  4  16   96
   10   |  6  30
  n \ k | 11  12   13   14   15   16   17   18   19
 ----------------------------------------------------
    2   | 176 144 630  756 1800 2048 7710 7776 27594
 Basic algebraic terms 

 Fermat theorem  

All classes with gcd(g,r)=1, r=n^k-1 are self-classes.
System G(n,k) has n^k instances.
If p ε P, only n instances (instances from G(n,1)) are nested to
the system G(n,p). All others classes are self-classes and have
k transpositions. Therefore p\(n^p-n), i.e. n^p-n=0(mod p), i.e. the
Fermat theorem.
Fermat quotient f(n,k) = ((n^(k-1))-1)/k
      k\n|       2 |        3
      ------------------------
       3 |       1 |        1
       5 |       3 |       16
       7 |       9 |      104
      11 |      93 |     5368
      13 |     315 |    40880
      17 |    3855 |  2532160
      19 |   13797 |      ...
      23 |   182361|      ...

 Instances of a given class

Let us evaluate the sum of instance numbers in all classes of G(3,3):
          0                0
          1   3   9       13
          2   6  18       26
          4  12  10       26
          5  15  19       39
          7  21  11       39
          8  24  20       52
         13               13
         14  16  22       52
         17  25  23       65
         26               26
Any of those sum is divisible by (n^k-1)/(n-1) = (3^3-1)/(3-1) = 13.

In  G(n,k), it holds for each class g(i):

     ∑ u(i,j) = 0  [ mod (n^k- 1)/(n-1)]
      j

 Class level

Let the level L(g) of a class g in G(n,k) is the sum of particular
numbers (digits) in any instance of the class.
It holds:
   L(g(i)) = k/q* ∑{j} u(i,j) / c(k,q)
where q is number of  transpositions (i.e. order of the original nested system)
and c(k,q) is nesting quotient.
For example in G(3,3):
       g|      | L(g)  |k/q|  ∑ uij
      --+------+-------+---+------
       0| 000  |  0    | 3 |    0
       1| 001  |  1    | 1 |   13
       2| 002  |  2    | 1 |   26
       4| 011  |  2    | 1 |   26
       5| 012  |  3    | 1 |   39
       7| 021  |  3    | 1 |   39
       8| 022  |  4    | 1 |   52
      13| 111  |  3    | 3 |   13
      14| 112  |  4    | 1 |   52
      17| 122  |  5    | 1 |   65
      26| 222  |  6    | 3 |   26
    ...
        L(7) = 3/3* 39/c(3,1) = 1*39/ ((3^3-1)/(3-1)) = 39/13 =3
        L(8) = 3/3* 52/c(3,1) = 1*52/ ((3^3-1)/(3-1)) = 52/13 =4
        ...
        L(13)= 3/1* 13/c(3,1) = 3*13/ ((3^3-1)/(3-1)) = 39/13 =3
        ...

    
Schematic algebra